package algorithm;

import java.util.Arrays;

/**
 * @author apple
 * @Classname PowerOfTwo
 * @Description 判断一个数是否为2的幂次方
 * @Date 2020/2/29 8:52
 */
public class PowerOfTwo {

    public static void main(String[] args) {
        isOdd(4);
        countingBits(5);

//        for (int i = 0; i < 10; i++) {
//            System.out.println(powerOfX(2, i));
//        }
        int n = 100000;

        /**求平方根 二分法**/
        System.out.println(sqr_1(n));

        /**求平方根 牛顿迭代法**/
        System.out.println(sqr_2(n));

        /**使用本地方法 native方法**/
        System.out.println(Math.sqrt(n));
    }

    /**
     * 位运算 被除数以2取模，相当于被除数和除数减一的与操作
     * 判断是否为偶数
     **/
    public static boolean isOdd(int x) {
        if ((x & (x - 1)) == 0) {
            System.out.println(true);
            return true;
        }
        System.out.println(false);
        return false;
    }

    /**
     * 一个非负整数n，计算0-n之间每个数的二进制数的1的个数
     **/
    public static int[] countingBits(int x) {
        int[] a = new int[x + 1];

        /**第0个数，固定为0，它的二进制数中的1的个数为0，因此，循环从i=1开始**/
        for (int i = 1; i < a.length; i++) {
            a[i] = a[i & (i - 1)] + 1;
        }
        for (int i = 0; i < a.length; i++) {
            System.out.println(i + "二进制数中的1的个数=" + a[i]);
        }
        Arrays.stream(a).forEach(System.out::println);
        return a;
    }

    /**
     * x的n次方
     **/
    public static double powerOfX(double x, int n) {
        double pow = 1;
        /**考虑n为负数**/
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
        while (n > 0) {
            if ((n & 1) == 0) {
                /**n为偶数，**/
                x = x * x;
                /**n除以2,位运算**/
                n >>= 1;
            } else {
                /**n为奇数**/
                pow = pow * x;
                n = n - 1;
            }
        }
        return pow;
    }

    /**
     * n的m次方 递归方法
     **/
    private static long power(int n, int m) {
        assert m >= 0;
        if (m == 0) {
            return 1;
        }
        if (m == 1) {
            return n;
        }
        long temp = power(n, m / 2);
        return m % 2 == 0 ? temp * temp : temp * temp * n;
    }

    /**
     * 求一个数的平方根
     * 方法一: 二分法
     */
    private static double sqr_1(int n) {
        if (n == 0 || n == 1) {
            return Double.valueOf(n);
        }
        int count = 0;
        double right = n;
        double left = 0;
        double mid = (right + left) / 2;
        double limit = 1e-4;
        while (Math.abs(right - left) > limit) {
            if (mid * mid > n) {
                right = mid;
            } else if (mid * mid < n) {
                left = mid;
            }
            count++;
            mid = (right + left) / 2;
        }
        System.out.println("count=" + count);
        return mid;
    }

    /**
     * 求平方根
     * 方法二:牛顿迭代法
     **/
    private static double sqr_2(int n) {
        int count = 0;
        double x1 = 1, x2;
        double limit = 1e-4;
        /** 牛顿迭代公式 f(x)=x^2-a **/
        x2 = x1 / 2.0 + n / (2 * x1);
        while (Math.abs(x2 - x1) > limit) {
            x1 = x2;
            //x2 = x1 / 2.0 + n / (2 * x1);
            x2 = (x1 + n / x1) / 2.0;
            count++;
        }
        System.out.println("count=" + count);
        return x2;
    }
}
